7 提升方法

#AdaBoost #ForwardStagewiseAlgorithm #Boosting #GBDT

参考这篇笔记了解 bagging&boosting 的基本概念. 在分类问题中, boosting 可以改变训练样本的权重, 学习多个分类器, 将他们进行线性组合.

1 AdaBoost 算法

1.1 基本思路

在满足 PAC 可学习性时, 我们可以定义

强可学习性: 存在多项式的学习算法可以较好的学习它;
弱可学习性: 学习的正确率仅好于随机猜测.

事实上可以证明, 强可学习和弱可学习等价, 因此我们需要把弱可学习 boost 为强可学习. 对于分类问题, 我们可以先学习一系列弱学习算法, 然后组合它们, 构成一个强分类器. AdaBoost 会每轮提高前一轮误分类样本的权值, 采取加权多数表决的方法.

1.2 AdaBoost 算法

依然假设训练集形如 $T = {(x_{1}, y_{1}), \dots, (x_{N}, y_{N})}$ , 其中 $x_{i} \in X \subset R^{n}, y_{i} \in Y = {- 1, + 1}$ .

AdaBoost 算法

输入 $T$ ; 弱学习算法.
输出最终分类器 $G (x)$ .

初始化权值分布 $D_{1}$ : $D_{1} = (ω_{11}, \dots, ω_{1 i}, \dots, ω_{1 N}), ω_{1 i} = \frac{1}{N}, i = 1, \dots, N .$
对于 $m = 1, \dots, M$ :
1. 使用权值分布为 $D_{m}$ 的训练集学习, 得到基本分类器 $G_{m} (x) : X \to {- 1, + 1} .$
2. 计算 $G_{m} (x)$ 的分类误差率 $e_{m} = \sum_{i = 1}^{N} P (G_{m} (x_{i}) \neq y_{i}) = \sum_{i = 1}^{N} ω_{m i} 1 {G_{m} (x_{i}) \neq y_{i}} .$
3. 计算 $G_{m} (x)$ 的系数 $α_{m} = \frac{1}{2} \log \frac{1 - e_{m}}{e_{m}}$ .
4. 更新权值分布 $\begin{aligned} D_{m + 1} & = (ω_{m + 1, 1}, \dots, ω_{m + 1, i}, \dots, ω_{m + 1, N}), \\ ω_{m + 1, i} & = \frac{1}{Z_{m}} ω_{m i} \exp (- α_{m} y_{i} G_{m} (x_{i})), \\ Z_{m} & = \sum_{i = 1}^{N} ω_{m i} \exp (- α_{m} y_{i} G_{m} (x_{i})) . \end{aligned}$
得到最终分类器 $\begin{aligned} f (x) & = \sum_{m = 1}^{M} α_{m} G_{m} (x), \\ G (x) & = sgn (f (x)) . \end{aligned}$

2 训练误差分析

定理 2.1 (AdaBoost 训练误差边界)

$\begin{matrix} (2.1) & \frac{1}{N} \sum_{i = 1}^{N} 1 {G (x_{i}) \neq y_{i}} \leq \frac{1}{N} \sum_{i = 1}^{N} \exp (- y_{i} f (x_{i})) = \prod_{m = 1}^{M} Z_{m} . \end{matrix}$

证明

当 $G (x_{i}) \neq y_{i}$ , $y_{i} f (x_{i}) < 0 \Rightarrow \exp (- y_{i} f (x_{i})) \geq 1$ , 从而第一个不等号成立.
对于等号, 根据 AdaBoost 算法的更新公式, 得到 $ω_{m i} \exp (- α_{m} y_{i} G_{m} (x_{i})) = Z_{m} ω_{m + 1, i},$ 从而 $\begin{aligned} \frac{1}{N} \sum_{i = 1}^{N} \exp (- y_{i} f (x_{i})) & = \frac{1}{N} \sum_{i = 1}^{N} (- \sum_{m = 1}^{M} α_{m} y_{i} G_{m} (x_{i})) \\ = \sum_{i = 1}^{N} ω_{1 i} \prod_{m = 1}^{M} \exp (- α_{m} y_{i} G_{m} (x_{i})) \\ = Z_{1} \sum_{i = 1}^{N} ω_{2 i} \prod_{m = 2}^{M} \exp (- α_{m} y_{i} G_{m} (x_{i})) \\ = \dots \\ = Z_{1} \dots Z_{m - 1} \sum_{i = 1}^{N} ω_{M i} \exp (- α_{M} y_{i} G_{M} (x_{i})) \\ = \prod_{m = 1}^{M} Z_{m} . \end{aligned}$

定理 2.2 (二分类问题的训练误差边界)

$\begin{matrix} (2.2) & \prod_{m = 1}^{M} Z_{m} = \prod_{m = 1}^{M} [2 \sqrt{e_{m} (1 - e_{m})}] = \prod_{m = 1}^{M} \sqrt{1 - 4 γ_{m}^{2}} \leq \exp (- 2 \sum_{m = 1}^{M} γ_{m}^{2}) . \end{matrix}$

其中 $γ_{m} = \frac{1}{2} - e_{m}$ .

证明

容易证明 $e^{x} \geq \sqrt{1 - x}, \forall x$ . 这样 $\prod_{m = 1}^{M} \sqrt{1 - 4 γ_{m}^{2}} \leq \exp (- 2 \sum_{m = 1}^{M} γ_{m}^{2}) .$ 这样根据算法中 $Z_{m}$ 的定义式 $\begin{aligned} Z_{m} & = \sum_{i = 1}^{N} ω_{m i} \exp (- α_{m} y_{i} G_{m} (x_{i})) \\ (2.3) & = \sum_{y_{i} = G_{m} (x_{i})} ω_{m i} e^{- α_{m}} + \sum_{y_{i} \neq G_{m} (x_{i})} ω_{m i} e^{α_{m}} \\ = (1 - e_{m}) e^{- α_{m}} + e_{m} e^{α_{m}} \\ = 2 \sqrt{e_{m} (1 - e_{m})} = \sqrt{1 - 4 γ_{m}^{2}}, \end{aligned}$
从而不等式得证.

推论

如果 $\exists γ > 0, \forall m : γ_{m} \geq γ$ , 则 $\begin{matrix} (2.4) & \frac{1}{N} \sum_{i = 1}^{N} 1 {G (x_{i}) \neq y_{i}} \leq \exp (- 2 M γ^{2}) . \end{matrix}$

这说明 AdaBoost 的训练误差是指数级下降的.

3 算法解释

3.1 前向分步算法 (Forward Stagewise Algorithm)

训练集 $T$ 同前. 考虑加法模型 $\begin{matrix} (3.1) & f (x) = \sum_{m = 1}^{M} β_{m} b (x; γ_{m}), \end{matrix}$ 这里 $b (x; γ_{m})$ 为基函数, $γ_{m}$ 为参数, $β_{m}$ 为系数. 给定训练数据和损失函数 $L (y, f (x))$ , 只需要考虑最小化问题 $min_{β_{m}, γ_{m}} \sum_{i = 1}^{N} L (y_{i}, \sum_{m = 1}^{M} β_{m} b (x_{i}; γ_{m})) .$
这是一个复杂的优化问题. 但是前向分步算法希望每步只学习一个基函数, 简化优化复杂度. 也即, 每步优化 $min_{β, γ} \sum_{i = 1}^{N} L (y_{i}; β b (x_{i}; γ)) .$

前向分步算法

输入 $T$ , $L (y, f (x))$ , ${b (x; γ)}$ .
输出加法模型 $f (x)$ .

初始化 $f_{0} (x) = 0$ .
对 $m = 1, \dots, M$ :
1. 极小化损失函数 $(β_{m}, γ_{m}) = \arg min_{β, γ} \sum_{i = 1}^{M} L (y_{i}, f_{m - 1} (x_{i}) + β b (x_{i}; y)),$ 得到 $β_{m}, γ_{m}$ .
2. 更新 $f_{m} (x) = f_{m - 1} (x) + β_{m} b (x; γ_{m}) .$
得到加法模型 $f (x) = f_{M} (x) = \sum_{m = 1}^{M} β_{m} b (x; γ_{m}) .$

3.2 前向分步算法与 AdaBoost

下面的定理指出前向分步算法可以推出 AdaBoost.

定理 3.1

AdaBoost 算法是基本分类器组成的加法模型, 损失函数是指数函数, 因此是前向分步算法的特例.

证明

由于 AdaBoost 的算法学习 $f (x) = \sum_{m = 1}^{M} α_{m} G_{m} (x),$ 这就是加法模型的结构, 因此只需要证明在损失函数是 $L (y, f (x)) = \exp [- y f (x)]$ 时, 表达式等价于 AdaBoost 的表达式.

假设经过 $m - 1$ 轮迭代的前向分步算法, 我们得到 $f_{m - 1} (x) = f_{m - 2} (x) + α_{m - 1} G_{m - 1} (x) = \sum_{i = 1}^{m - 1} α_{i} G_{i} (x),$ 且在第 $m$ 轮迭代希望得到 $α_{m}, G_{m} (x), f_{m} (x)$ : $f_{m} (x) = f_{m - 1} (x) + α_{m} G_{m} (x),$ 也即 $\begin{aligned} (α_{m}, G_{m} (x)) & = \arg min_{α, G} \sum_{i = 1}^{N} \exp [- y_{i} (f_{m - 1} (x_{i}) + α G (x_{i}))] \\ = \arg min_{α, G} \sum_{i = 1}^{N} {\overset{―}{ω}}_{m i} \exp [- y_{i} α G (x_{i})], \end{aligned}$
其中 ${\overset{―}{ω}}_{m i} = \exp [- y_{i} f_{m - 1} (x_{i})]$ , 与最小化无关. 在这个优化问题中, $G_{m}^{*} (x) = \arg min_{G} \sum_{i = 1}^{N} {\overset{―}{ω}}_{m i} 1 {y_{i} \neq G (x_{i})},$ 它就是 AdaBoost 中的 $G_{m} (x)$ . 然后, 参考 (2.3), $\begin{aligned} \sum_{i = 1}^{N} {\overset{―}{ω}}_{m i} \exp [- y_{i} α G (x_{i})] = \sum_{y_{i} = G_{m} (x_{i})} {\overset{―}{ω}}_{m i} e^{- α} + \sum_{y_{i} \neq G_{m} (x_{i})} {\overset{―}{ω}}_{m i} e^{α} \\ (*) & = & (e^{α} - e^{- α}) \sum_{i = 1}^{N} {\overset{―}{ω}}_{m i} 1 {y_{i} \neq G (x_{i})} + e^{- α} \sum_{i = 1}^{N} {\overset{―}{ω}}_{m i} . \end{aligned}$
定义分类误差率 $e_{m} = \frac{\sum_{i = 1}^{N} {\overset{―}{ω}}_{m i} 1 {y_{i} \neq G_{m} (x_{i})}}{\sum_{i = 1}^{N} {\overset{―}{ω}}_{m i}} = \sum_{i = 1}^{N} ω_{m i} 1 {y_{i} \neq G_{m} (x_{i})},$ 则带入已得到的 $G_{m}^{*} (x)$ , 对 (*) 关于 $α$ 求导, 得到 $α_{m}^{*} = \frac{1}{2} \log \frac{1 - e_{m}}{e_{m}} .$ 它就是 AdaBoost 中的 $α_{m}$ .
最后, 考察权值的更新. 由 $f_{m} (x) = f_{m - 1} (x) + α_{m} G_{m} (x)$ , 带入 ${\overset{―}{ω}}_{m i}$ , 得 ${\overset{―}{ω}}_{m + 1, i} = {\overset{―}{ω}}_{m, i} \exp [- y_{i} α_{m} G_{m} (x)],$ 最后加上规范化因子就全部等价了.

4 提升树

基于分类树或者回归树基本分类器, 用前向分步算法得到的模型称为提升树 (Boosting Tree), 它是统计学习中性能最好的方法之一.

4.1 提升树模型

用 $T (x; Θ_{m})$ 表示决策树, $Θ_{m}$ 为参数, $M$ 为数的个数, 则提升树模型可以表示为 $\begin{matrix} (4.1) & f_{M} (x) = \sum_{m = 1}^{M} T (x; Θ_{m}) . \end{matrix}$

4.2 提升树算法

代入前向分步算法, 得到 $\begin{aligned} f_{m} (x) & = f_{m - 1} (x) + T (x; Θ_{m}), \\ (4.2) & {\hat{Θ}}_{m} & = \arg min_{Θ_{m}} \sum_{i = 1}^{N} L (y_{i}, f_{m - 1} (x_{i}) + T (x_{i}; Θ_{m})) . \end{aligned}$
对于二分类问题, 将 $G_{m} (x)$ 限制为二分类树即可, 这就是 AdaBoost 算法的特殊情况. 接下来讨论回归问题的提升树.
现在对于 $T$ , 需要更改 $y_{i} \in Y \subset R$ . 回顾回归树, 将 $X$ 划分为 $J$ 个不相交的区域 $R_{1}, \dots, R_{J}$ , 在每个区域上确定输出的常量 $c_{j}$ , 则 $\begin{matrix} (4.3) & T (x; Θ) = \sum_{j = 1}^{J} c_{j} 1 {x \in R_{j}}, \end{matrix}$ 其中 $Θ = {(R_{1}, c_{1}), \dots, (R_{J}, c_{J})}$ , $J$ 就是树的叶节点个数.

如果采用平方误差损失函数 $L (y, f (x)) = (y - f (x))^{2}$ , 则代入 (4.2) $L (y, f_{m - 1} (x) + T (x; Θ_{m})) = [r - T (x; Θ_{m})]^{2},$ 这里 $r = y - f_{m - 1} (x)$ 是当前拟合数据的残差. 所以, $T$ 的目标仅仅是拟合当前模型的残差.

回归问题的提升树算法

输入 $T$
输出 $f_{M} (x)$

初始化 $f_{0} (x) = 0$ .
对 $m = 1, \dots, M$ ,
1. 按 (4.3) 计算残差 $r_{m i} = y_{i} - f_{m - 1} (x_{i}), 1 \leq i \leq N$ .
2. 拟合 $r_{m i}$ 学习回归树 $T (x; Θ_{m})$ .
3. 更新 $f_{m} (x) = f_{m - 1} (x) + T (x; Θ_{m})$ .
得到 $f_{M} (x) = \sum_{m = 1}^{M} T (x; Θ_{m})$ .

4.3 梯度提升

对于一般损失函数, 每一步的优化可能并非像平方损失函数那样容易. 因此, 可以使用梯度提升 (gradient boosting), 关键是利用损失函数的负梯度在当前模型的取值 $- {[\frac{\partial L (y, f (x_{i}))}{\partial f (x_{i})}] |}_{f (x) = f_{m - 1} (x)} .$

梯度提升算法

输入 $T$ , $L (y, f (x))$ .
输出回归树 $\hat{f} (x)$ .

初始化 $f_{0} (x) = \arg min_{c} \sum_{i = 1}^{N} L (y_{i}, c) .$
对 $m = 1, \dots, M$ ,
1. 对 $n = 1, \dots, N$ , 计算 $r_{m i} = - {[\frac{\partial L (y, f (x_{i}))}{\partial f (x_{i})}] |}_{f (x) = f_{m - 1} (x)} .$
2. 对 $r_{m i}$ 拟合回归树, 得到第 $m$ 棵树对叶结点区域为 $R_{m j}, 1 \leq j \leq J$ .
3. 对 $j = 1, \dots, J$ , 计算 $c_{m j} = \arg min_{c} \sum_{x_{i} \in R_{m j}} L (y_{i}, f_{m - 1} (x_{i}) + c) .$
4. 更新 $f_{m} (x) = f_{m - 1} (x) + \sum_{j = 1}^{J} c_{m j} 1 {x \in R_{m j}}$ .
得到回归树 $\hat{f} (x) = f_{M} (x) = \sum_{m = 1}^{M} \sum_{j = 1}^{J} c_{m j} 1 {x \in R_{m j}} .$